#ifndef MERGE_H_
#define MERGE_H_

#include <cstddef>
#include <cstdint>
#include <type_traits>
#include <vector>
#include <xutility>

namespace lxj
{
// 归并排序递归版
template<class Iter>
void merge(Iter first, Iter mid, Iter last)
{
    if (first == last) return;

    using type                       = std::decay_t<decltype(*first)>;
    constexpr size_t help_size       = 100001;
    static type      help[help_size] = {};

    Iter   l = first, m = mid, r = last;
    size_t i = 0;
    while (i < help_size && l != m && m != r) {
        help[i++] = *l < *m ? *l++ : *m++;
    }

    while (l != mid) {
        help[i++] = *l++;
    }
    while (m != last) {
        help[i++] = *m++;
    }

    l = first;
    for (size_t j = 0; j < i; j++) {
        *l++ = help[j];
    }
}

template<class Iter>
void merge_sort1(Iter first, Iter last)
{
    std::_Adl_verify_range(first, last);

    auto ufirst = std::_Get_unwrapped(first);
    auto ulast  = std::_Get_unwrapped(last);
    using type  = std::remove_cv_t<std::remove_pointer_t<std::decay_t<decltype(first)>>>;
    static_assert(std::is_arithmetic_v<type> && !std::is_same_v<type, char>,
                  "此函数只支持整数与浮点数");

    if (ulast - ufirst <= 1) return;

    size_t s   = ulast - ufirst;
    auto   mid = ufirst + (ulast - ufirst) / 2;
    merge_sort1(ufirst, mid);
    merge_sort1(mid + 1, ulast);
    merge(first, mid, last);
}

// 归并排序非递归版
template<class Iter>
void merge_sort2(Iter first, Iter last)
{
    std::_Adl_verify_range(first, last);

    auto ufirst = std::_Get_unwrapped(first);
    auto ulast  = std::_Get_unwrapped(last);
    using type  = std::remove_cv_t<std::remove_pointer_t<std::decay_t<decltype(ufirst)>>>;
    static_assert(std::is_arithmetic_v<type> && !std::is_same_v<type, char>,
                  "此函数只支持整数与浮点数");

    decltype(ufirst) l, m, r;
    for (size_t step = 1; step < (ulast - ufirst); step <<= 1) {
        l = ufirst;
        while (ulast - l > 0) {
            m = l + step;
            if (m + 1 >= ulast) break;
            bool b = ulast - (l + (step << 1)) >= 0;
            r      = b ? l + (step << 1) : ulast;
            merge(l, m, r);
            l = r;
        }
    }
}

// 求小和
template<class Iter>
long double merge_sum(Iter first, Iter mid, Iter last)
{
    long double ans = 0;
    long double sum = 0;
    for (Iter i = first, j = mid + 1; j <= last; j++) {
        while (i != mid + 1 && *i <= *j) {
            sum += *i++;
        }
        ans += sum;
    }

    using type                       = std::decay_t<decltype(*first)>;
    constexpr size_t help_size       = 100001;
    static type      help[help_size] = {};

    Iter   l = first, m = mid, r = last;
    size_t i = 0;
    while (i < help_size && l != m && m != r) {
        help[i++] = *l < *m ? *l++ : *m++;
    }

    while (l != mid) {
        help[i++] = *l++;
    }
    while (m != last) {
        help[i++] = *m++;
    }

    l = first;
    for (size_t j = 0; j < i; j++) {
        *l++ = help[j];
    }

    return ans;
}

template<class Iter>
long double small_sum(Iter first, Iter last)
{
    std::_Adl_verify_range(first, last);

    auto ufirst = std::_Get_unwrapped(first);
    auto ulast  = std::_Get_unwrapped(last);
    using type  = std::remove_cv_t<std::remove_pointer_t<std::decay_t<decltype(ufirst)>>>;
    static_assert(std::is_arithmetic_v<type> && !std::is_same_v<type, char>,
                  "此函数只支持整数与浮点数");

    if (ulast == ufirst) return 0;

    auto mid = ufirst + (ulast - ufirst) / 2;
    return small_sum(ufirst, mid) + small_sum(mid + 1, ulast) + merge_sum(ufirst, mid, ulast);
}

// 翻转对，力扣493
/*
    给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
    你需要返回给定数组中的重要翻转对的数量。
*/
template<class T, std::enable_if_t<std::is_arithmetic_v<T>, int> = 0>
inline int count_merge(std::vector<T>& nums, int l, int m, int r)
{
    int ans = 0, sum = 0;
    for (int j = l, i = m + 1; j <= m; j++) {
        while (i <= r && (int64_t)nums[i] * 2 < (int64_t)nums[j]) {
            sum++;
            i++;
        }
        ans += sum;
    }

    constexpr int help_size       = 500001;
    static int    help[help_size] = {};

    size_t i  = 0;
    int    _l = l, _m = m + 1, _r = r;
    while (_l <= m && _m <= _r) {
        help[i++] = nums[_l] <= nums[_m] ? nums[_l++] : nums[_m++];
    }

    while (_l <= m) {
        help[i++] = nums[_l++];
    }

    while (_m <= r) {
        help[i++] = nums[_m++];
    }

    for (int j = 0; j < i; j++) {
        nums[l + j] = help[j];
    }

    return ans;
}

template<class T, std::enable_if_t<std::is_arithmetic_v<T>, int> = 0>
inline int count(std::vector<T>& nums, int left, int right)
{
    if (left == right) return 0;

    int mid = left + (right - left) / 2;
    return count(nums, left, mid) + count(nums, mid + 1, right) +
           count_merge(nums, left, mid, right);
}

template<class T, std::enable_if_t<std::is_arithmetic_v<T>, int> = 0>
inline int reverse_pair(std::vector<T>& nums)
{
    return count(nums, 0, nums.size() - 1);
}


}   // namespace lxj

#endif